package leetcode;
/**
 * 234.回文链表
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false
 * 输入：head = [1,2,2,1]
 * 输入：head = [1,2,3,2,1]
 * 输出：true
 * 输入：head = [1,2]
 * 输出：false
 */
public class Num_234 {
    /** 方法一：切开一半比较 **/
    //先找中间节点，把后半段链表反转，再和前半段作比较
    public boolean isPalindrome(ListNode head) {
        if(head.next == null){
            return true;
        }
        //先找中间节点
        ListNode fast = head;
        ListNode low = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            low = low.next;
        }
        //此时low位于中间节点
        //把以low为头节点的链表反转
        ListNode prev = null;
        ListNode cur = low;
        ListNode next = cur.next;
        while(cur != null){
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        //此时反转后的链表的头节点是prev
        //和原链表作比较
        ListNode node = head;
        while(prev != null){
            if(prev.val != node.val){
                return false;
            }
            prev = prev.next;
            node = node.next;
        }
        return true;
    }

    /** 方法二：新建它的反转链表，跟原链表比较 **/
    public boolean isPalindrome2(ListNode head){
        //虚拟节点，用于连接新链表
        ListNode dummyHead = new ListNode(-1);
        //temp暂存head，防止head最后跑丢
        ListNode temp = head;
        while(temp != null){
            //头插法
            ListNode node = new ListNode(temp.val);
            node.next = dummyHead.next;
            dummyHead.next = node;
            temp = temp.next;
        }
        //比较新链表和旧链表是否一样
        ListNode newHead = dummyHead.next;
        while(head != null){
            if(head.val != newHead.val){
                return false;
            }
            head = head.next;
            newHead = newHead.next;
        }
        return true;
    }
}
